992. Subarrays with K Different Integers

Description

Solution

Quite tricky solution using two pointers, that we can fix the right pointer then move the left pointer to check the subarrays with less equals k elements. Then we can get subarray number by number of array with less equals k+1 elemens - number of array with less equals k+1 elemens.

Code

class Solution {
public:
    int subarraysWithKDistinct(vector<int>& nums, int k) {
        return getLEK(nums, k) - getLEK(nums,k-1);
    }

    int getLEK(vector<int>& nums, int k){
        unordered_map<int,int> bucket;
        int cnt = 0, l = 0, res = 0;
        for(int i = 0; i < nums.size(); i++){
            if(++bucket[nums[i]] == 1)
                cnt++;
            if(cnt <= k)
                ;
            // bucket.size() > k
            else{
                while(cnt > k){
                    if(--bucket[nums[l++]] == 0)
                        cnt--;
                }
            }
            res += i - l;
        }
        return res;
    }
};